﻿// Algo.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include"data_structure.h"

void INSERTION_SORTY(int A[],int);
void Merge(int A[],int,int,int);
void mergeSort(int A[],int,int);

//
struct Reslt;
Reslt maxCrossingSubArr(int A[], int low, int mid, int high);
Reslt Find_MaxSubArray(int A[], int low, int high);
void test1();
void test3();
void test4();
void test5();
void test6();
void test7();
void test8();
int main()
{
	test8();
}

void test()
{
	int a[] = { 2,5,10,89,4,7,13,24,65,91,3,6,19,1,2,3,3,3,479 };
	//INSERTION_SORTY(a,sizeof(a)/sizeof(int));
	mergeSort(a, 0, 13);
	for (int i = 0; i < sizeof(a) / sizeof(int); i++) {
		std::cout << a[i] << "  ";
	}
	std::cout << "\n";
	std::cout << "Hello World!\n";
	
}

struct Reslt {
	int low;
	int high;
	double SUM;
};
void test1()
{
	int a[] = { 2,5,-10,89,4,-7,-13,24,65,-91,-3,6,19,1,2,-3,3,-3,-479 };
	Reslt re = Find_MaxSubArray(a,0,18);
	for (int i = re.low; i <= re.high; i++) {
		std::cout << a[i] << "  ";
	}
	std::cout << "\n";
	std::cout << "sum="<< re.SUM;
}
// 插入排序
void INSERTION_SORTY(int A[],int size)
{
	for (int j = 1; j < size; j++)
	{
		//取出要排序的元素
		int currK = A[j];
		//要放置的位置
		int i = j - 1;
		while(i>=0&&A[i]>currK){
			A[i+1]= A[i];
			i--;
		}
		A[i + 1] = currK;
	}
}
//归并排序
void Merge(int A[], int p, int q, int r)
{
	int N1 = q - p + 1;
	int N2 = r - q;
	int Larr[512] = {};
	int Rarr[512] = {};

	for (int i = 0; i < N1; i++) 
		Larr[i]=A[p+i];	
	for (int j = 0; j < N2; j++) 
		Rarr[j] = A[q+1+j];
	
	Larr[N1] = 999999;
	Rarr[N2] = 999999;
	int L = 0;
	int R = 0;
	for (size_t i=p; i<=r; i++)
	{
		if (Larr[L] <= Rarr[R]) {
			A[i] = Larr[L];
			L++;
		}
		else {
			A[i]=Rarr[R];
			R++;
		}
	}
}
void mergeSort(int A[],int p,int r)
{
	if (p < r){
		int q = floor((p+r)/2);
		mergeSort(A,p,q);
		mergeSort(A,q+1,r);
		Merge(A,p,q,r);
	}	
}
//MAX_subARR

Reslt maxCrossingSubArr(int A[], int low, int mid, int high)
{
	double left_sum = INT_MIN;
	double Lsum = 0;
	int max_left = -1;
	for (int i = mid; i >= low;i--) {
		Lsum += A[i];
		if (Lsum> left_sum)
		{
			left_sum = Lsum;
			max_left = i;
		}
	}
	double right_sum = INT_MIN;
	double Rsum = 0;
	int max_right = -1;
	for (int j= mid+1; j<= high; j++) {
		Rsum += A[j];
		if (Rsum > right_sum)
		{
			right_sum = Rsum;
			max_right = j;
		}
	}	
	return Reslt{ max_left ,max_right ,left_sum+right_sum };
}

Reslt Find_MaxSubArray(int A[],int low,int high)
{
	if (low==high)
		return Reslt{ low,high,A[low]+0. };
	int mid = floor((low+high)/2);
	Reslt Lre=Find_MaxSubArray(A, low, mid);
	Reslt Rre=Find_MaxSubArray(A, mid+1, high);
	Reslt CROSSArr= maxCrossingSubArr(A, low,mid, high);
	if (Lre.SUM>= Rre.SUM&& Lre.SUM >= CROSSArr.SUM)
	{
		//std::cout << "this Lre";
		return Lre;
	}else if(Rre.SUM >= Lre.SUM && Rre.SUM >= CROSSArr.SUM){
		//std::cout << "this Rre";
		return Rre;
	}else
	{
		//std::cout << "this cross";
		return CROSSArr;
	}
}
//堆排序
void swap(int& A, int& B) {
	int tmp = A;
	A = B;
	B = tmp;
}
//大堆化指定节点
void Max_heapify(int A[], unsigned I, unsigned _size)
{
	int L = -1;
	int R = -1;
	if (0 == I) {
		L = 1;
		R = 2;
	}else
	{
		L = 2 * I+1;
		R = L + 1;
	}
	int largest = -1;
	if (L <_size && A[L] > A[I])
		largest = L;
	else
		largest = I;
	if (R <_size && A[R] > A[largest])
		largest = R;
	if (largest != I) {
		swap(A[I], A[largest]);
		Max_heapify(A, largest, _size);
	}
		
}

void Build_M_heap(int A[], unsigned _size)
{
	for (int i =floor(_size/2); i >=0; i--)
	{
		Max_heapify(A, i, _size);
	}
}

void test3()
{
	int a[] = { -200,150,170,89,4,-7,-13,24,35,-91,-3,6,119,1,2,-3,3,-3,79 };

	Build_M_heap(a, sizeof(a) / sizeof(int));

	for (int i = 0; i < sizeof(a) / sizeof(int); i++) {
		std::cout << a[i] << "  ";
	}
	std::cout << "\n";
	std::cout << "Hello World!\n";
}

void HeapSort(int A[], unsigned _size)
{
	Build_M_heap(A, _size);
	for (int i = _size-1; i >0; i--)
	{
		swap(A[i], A[0]);
		int tmp = _size ;
		Max_heapify(A,0, i);

		std::cout << A[i] << "  size:"<< i <<"  i:"<<i<<"\n";
	}
}
void test4()
{
	int a[] = { -200,150,170,89,4,-7,-13,24,35,-91,-3,6,119,1,2,-3,3,-3,79 };

	HeapSort(a, sizeof(a) / sizeof(int));

	for (int i = 0; i < sizeof(a) / sizeof(int); i++) {
		std::cout << a[i] << "  ";
	}
	std::cout << "\n";
	std::cout << "Hello World!\n";
}

//最大优先队列

int  Heap_Maximum(int A[])
{
	return A[0];
}

int Heap_Extract_Max(int A[], unsigned _size)
{
	if (_size < 1)
		return INT_MIN;
	int max = A[0];
	A[0] = A[_size-1];
	Max_heapify(A,0,_size-1);
	return max;
}

inline int parent(int I){
	if (I <= 0)
	return -1;
	else
	return floor(I/2);
}
void heap_Increase_key(int A[],int index,int key)
{
	if(key < A[index])
		return;
	A[index] = key;	
	int parI=index;
	int tpI=index;
	while (tpI>0&&A[tpI]>A[parent(tpI)])
	{
		swap(A[tpI],A[tpI]);
		tpI = parent(tpI);
	}
}

void Max_Heap_insert(int A[],unsigned _size, int key)
{
	
	int* TMP = new int[(_size+1)*sizeof(int)];
	memcpy(TMP,A,_size*sizeof(int));
	TMP[_size+1]=INT_MIN;
	heap_Increase_key(TMP, _size,key);
	
	for (int i = 0; i <_size+1; i++) {
		std::cout << TMP[i] << "  ";
	}
	std::cout << "\n";
	std::cout << "Hello World!\n";
}

void test5()
{
	int* a = new int[19*sizeof(int)]{-200,150,170,89,4,-7,-13,24,35,-91,-3,6,119,1,2,-3,3,-3,79};

	HeapSort(a,19);
	Max_Heap_insert(a,19, 500);
	for (int i = 0; i < 19; i++) {
		std::cout << a[i] << "  ";
	}
	std::cout << "\n";
	std::cout << "Hello World!\n";
}
//快排

int partition(int* A, int p, int r)
{
	int ENDv = A[r];
	int jmp = p - 1;
	for (int j= p; j<=r-1;j++) {
		if (A[j]<= ENDv) {
			jmp++;
			swap(A[jmp], A[j]);
		}	
	}
	swap(A[jmp+1], A[r]);
	return jmp + 1;
}

void QuickSort(int* A, int p, int r)
{
	if (p >= r)
		return;
	int q = partition(A, p, r);
	QuickSort(A,p,q-1);
	QuickSort(A, q+1, r);
}

void test6()
{
	int* a = new int[19 * sizeof(int)]{ 3,10,7,9,4,7,-3,4,5,-9,3,6,9,1,2,-3,8,-3,7};

	QuickSort(a, 0, 18);
	for (int i = 0; i < 19; i++) {
		std::cout << a[i] << "  ";
	}
	std::cout << "\n";
	std::cout << "Hello World!\n";
}


//计数排序
void Counting_Sort(int* A, int* B,int k,int length)
{
	double lk = k;
	int* C = new int[sizeof(int)*(lk+1)];
	
	for (int i=0; i < (k + 1); i++)
	{
		*(C+i)=0;
	}
	for(int i=0; i<length; i++)
	{
		*(C+*(A+i))+=1;		
	}
	for (int i = 0; i <(k+1); i++)
	{
		std::cout << *(C+i) << "  value  " << i << "  i\n";
	}
	for (int i = 1; i<(k+1); i++)
	{
		*(C+i)+= *(C+i-1);
	}
	for (int i = 0; i < (k + 1); i++)
	{
		std::cout << *(C+i) << "  value  " << i << "  i\n";
	}
	for (int j = length-1;j>=0;j--)
	{
		//std::cout << *(A+j) << "  value  " << j<< "  j\n";
		*(B+*(C+*(A+j))-1) = *(A+j);
		*(C + *(A + j))-=1;
	}

	delete[] C;
}

void test7()
{
	int* a = new int[19* sizeof(int)]{3,10,7,9,4,7,13,4,5,9,3,6,9,1,2,3,8,3,7};
	int* b = new int[19* sizeof(int)]{};
	Counting_Sort(a, b, 113, 19);
	for (int i = 0; i < 19; i++) {
		std::cout << b[i] << "  ";
	}
	std::cout << "\n";
	std::cout << "Hello World!\n";
}

void test8()
{
	stack stk;
	stk.push(0);
	stk.push(6);
	stk.push(56);
	stk.push(68);
	stk.push(-6);

	while (stk.size()>0)
	{
		std::cout << *stk.pop() << "\n";
	}
}




